package heap;

import java.util.Arrays;

public class PriorityQueue {
    public static void main(String[] args) {
        int[]arr={27,15,19,18,28,34,65,49,25,37};
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.createHeap(arr);
        priorityQueue.display();
        priorityQueue.push(100);
        priorityQueue.display();
        priorityQueue.pollHeap();
        priorityQueue.display();

    }
    public int[] elem;
    public int usedSize;
    int CAPICITY_SIZE=10;
 
    public PriorityQueue() {
        elem=new int[CAPICITY_SIZE];
        this.usedSize=0;
    }
 
    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        this.elem = Arrays.copyOf(array, array.length);
        this.usedSize = array.length;
        //定义父节点下标
        int root= (array.length-1-1)/2;
        for (int i = root; i >=0; i--) {
            shiftDown(i, array.length);
        }
    }
 
    /**
     *
     * @param root 是每棵子树的根节点的下标
     * @param len  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int root,int len) {
        //定义子节点
        int child=(2*root)+1;
        while(child<len){
            //判断是否存在右子结点
            if(child+1<len){
                if(elem[child]<elem[child+1]){
                    child+=1;
                }
            }
            //对父子结点进行交换
            if(elem[root]<elem[child]){
                swap(elem,root,child);
            }
            root=child;
            child=(root*2)+1;
        }
    }

    private void swap(int []arr,int i, int j) {
        int tmep=arr[i];
        arr[i]=arr[j];
        arr[j]=tmep;
    }


    /**
     * 入队：仍然要保持是大根堆
     * @param val
     */
    public void push(int val) {
        //在入队时应该从下到上进行调整，在遇到父节点的值比子节点的值大或者到达堆顶时结束
        //在入队时应先检查是否队列已满
        if (isFull()){
            //进行扩容
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        //将节点加入队列
        elem[usedSize++]=val;
        //将孩子结点下标进行储存
        int child=usedSize-1;
        //不断进行向上调整
        shiftUp(child);


    }
 
    private void shiftUp(int child) {
        //定义父节点
        int root=(child-1)/2;
        //进行遍历
        while(child>0&&root>=0){
            if(elem[child]>elem[root]){
                swap(elem,child,root);
            }
            else{
                //退出循环
                break;
            }
            //不断进行向上循环
            child=root;
            root=(child-1)/2;
        }

    }
 
    public boolean isFull() {
        return usedSize== elem.length;
    }
 
    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     * 思路如下：每次将要删除的结点和堆根结点进行对调，然后将UsedSize--,然后进行向下遍历
     */
    public void pollHeap() {
        //判断堆是否为空
        if(isEmpty()){
            throw new RuntimeException("堆中没有元素，无法取出顶部元素");
        }
        //交换父子结点
        swap(elem,0,usedSize-1 );
        usedSize--;
        shiftDown(0,usedSize);
    }
 
    public boolean isEmpty() {
        return usedSize==0;
    }
 
    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {
        if (usedSize==0){
            throw new RuntimeException("堆为空，无法取出堆顶元素");
        }
        return elem[0];
    }
    public void display(){
        //建立sb
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        //循环遍历加元素
        for (int i = 0; i <usedSize ; i++) {
            sb.append(elem[i]);
            if(i!=usedSize-1){
                sb.append(", ");
            }
        }
        sb.append("]");
        System.out.println(sb);
    }
}